// 递归方法
; (function () {
    //return
    /**
   * Definition for a binary tree node.
   * function TreeNode(val, left, right) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.left = (left===undefined ? null : left)
   *     this.right = (right===undefined ? null : right)
   * }
   */
    /**
     * @param {TreeNode} root
     * @return {boolean}
     */
    var isSymmetric = function (root) {

        let leftRes = []
        let rightRes = []

        leftRightSort(root.left, leftRes)
        rightLeftSort(root.left, rightRes)

        let len = leftRes

        for (let index = 0; index < len; index++) {
            if (leftRes[index] !== rightRes[index]) {
                return false
            }

        }
        return true
    };

    // 左右中后序
    function leftRightSort(root, res) {
        if (!root) return null

        leftRightSort(res.left)
        leftRightSort(res.right)
        res.push(root.val)
    }
    // 右左中后序
    function rightLeftSort(root, res) {
        if (!root) return null

        leftRightSort(res.right)
        leftRightSort(res.left)
        res.push(root.val)
    }
})();
// 迭代方法
; (function () {
    //return
    /**
   * Definition for a binary tree node.
   * function TreeNode(val, left, right) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.left = (left===undefined ? null : left)
   *     this.right = (right===undefined ? null : right)
   * }
   */
    /**
     * @param {TreeNode} root
     * @return {boolean}
     */
    var isSymmetric = function (root) {
        let leftQueue = [root.left]
        let rightQueue = [root.right]

        while (leftQueue.length || rightQueue.length) {
            // 当前层的队列
            let leftLen = leftQueue.length
            let rightLen = rightQueue.length
            // 当前层的valList
            let leftList = []
            let rightList = []


            for (let index = 0; index < leftLen; index++) {
                let current = leftQueue.shift()

                if (!current) {
                    leftList.push(null)
                    continue
                }

                leftList.push(current.val)
                leftQueue.push(current.left)
                leftQueue.push(current.right)


            }

            for (let index = 0; index < rightLen; index++) {
                let current = rightQueue.shift()
                if (!current) {
                    rightList.push(null)
                    continue
                }

                rightList.push(current.val)
                rightQueue.push(current.right)
                rightQueue.push(current.left)

            }
            console.log(leftList, rightList);
            if (leftList.length !== rightList.length) return false

            for (let index = 0; index < leftList.length; index++) {
                if (leftList[index] !== rightList[index]) {
                    console.log(leftList[index], rightList[index]);
                    return false
                }
            }
        }

        return true
    };
})();